{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "613925c4",
   "metadata": {},
   "source": [
    "# 分治的作业"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfb685c2",
   "metadata": {},
   "source": [
    "## 2-4  \n",
    "1. (2,1),(3,1),(8,6),(8,1),(6,1)  \n",
    "2. 从大到小降序排列；$\\frac{n(n-1)}{2}$个。\n",
    "3. $\\because$ 插入排序每进行一次while循环就消除一个逆序对    \n",
    "   $\\therefore$ 设有$k$个逆序对，$n$个数，就需要进行$k+n$次运算   \n",
    "4. 程序如下，时间复杂度：$$T(n)=2T(\\frac{n}{2})+\\Theta(n)$$  $$T(n)=\\Theta(nlgn)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "17c3cc32",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['2', '3', '8', '6', '1']\n",
      "共有5对逆序对\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "a_str = input().split()\n",
    "a = [int(i) for i in a_str]\n",
    "\n",
    "def find_inversion(a:list, left:int, right:int):\n",
    "    mid = (right+left)//2\n",
    "    ans = 0\n",
    "    if left<right:\n",
    "        ans += find_inversion(a, left, mid)\n",
    "        ans += find_inversion(a, 1+mid, right)\n",
    "    elif left == right:\n",
    "        return 0\n",
    "    \n",
    "    # 计算跨过中点的逆序对\n",
    "    i,j = mid, right\n",
    "    while i>=left and j>mid:\n",
    "        if a[i]<=a[j]:\n",
    "            j -= 1\n",
    "        else:\n",
    "            i -= 1\n",
    "            ans += j - mid\n",
    "    \n",
    "    # 排序\n",
    "    temp = []\n",
    "    i,j = left,min(1+mid,right)\n",
    "    while i<=mid and j<=right:\n",
    "        if a[i]<a[j]:\n",
    "            temp.append(a[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            temp.append(a[j])\n",
    "            j += 1\n",
    "    if i>mid and j<=right:\n",
    "        temp.extend(a[j:1+right])\n",
    "    elif j>right and i<=mid:\n",
    "        temp.extend(a[i:1+mid])\n",
    "    a[left:1+right] = temp\n",
    "    return ans\n",
    "\n",
    "print(a_str)\n",
    "print(\"共有{}对逆序对\".format(find_inversion(a,0,n-1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e46a17c0",
   "metadata": {},
   "source": [
    "## 4.3-2   \n",
    "设 $T\\leq clgn$,则\n",
    "$$T(n)=T(\\lceil \\frac{n}{2} \\rceil)+1\\\\\n",
    "\\leq clg(\\lceil \\frac{n}{2} \\rceil)+1\\\\\n",
    "\\leq clg(\\frac{n}{2})+1\\\\\n",
    "\\leq clgn-clg2+1\\\\\n",
    "\\leq clgn$$\n",
    "$\\therefore$ 取 $c> \\frac{1}{lg2}$ 即可证明"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28899ba8",
   "metadata": {},
   "source": [
    "## 4.3-9\n",
    "设$t=lgn$，则$T(2^t)=3T(2^{\\frac{t}{2}})+t$\n",
    "\n",
    "设$S(t)=T(2^t)$，则$S(t)=3S(\\frac{t}{2})+t$\n",
    "\n",
    "由主方法，\n",
    "$\\because t = O(n^{log_2 3-0.01}) \\therefore S(t)= \\Theta(t^{log_2 3})$\n",
    "\n",
    "$\\therefore T(n)=\\Theta((lgn)^{log_2 3})$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8863b56d",
   "metadata": {},
   "source": [
    "## 4.4-6  \n",
    "<!-- ![pic](\\images\\4-4.6.png)   -->\n",
    "<img src=\"./images/4-4.6.png\" width=50%>\n",
    "\n",
    "深度：$h=\\Theta(lgn)$ 叶子节点：$l(n)=\\Theta(n)$\n",
    "\n",
    "$\\therefore T(n)=\\Theta(nlgn)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3b75a59",
   "metadata": {},
   "source": [
    "## 4-5.1\n",
    "1. $$T(n)=2T(\\frac{n}{4})+1$$\n",
    "   $$f(n)=\\Theta(1)=O(n^{lg_4 2 -0.01})$$\n",
    "   $$\\therefore T(n)=\\Theta(\\sqrt n)$$\n",
    "\n",
    "2. $$T(n)=2T(\\frac{n}{4})+\\sqrt n$$\n",
    "   $$f(n)=\\Theta(\\sqrt n)=O(n^{log_4 2}*lg^0 n)$$\n",
    "   $$\\therefore T(n)=\\Theta(\\sqrt n lgn)$$\n",
    "\n",
    "3. $$T(n)=2T(\\frac{n}{4})+n$$\n",
    "   $$f(n)=\\Theta(n)=\\Omega(n^{lg_4 2 +c})$$\n",
    "   且$2* \\frac{n}{4} \\leq cn \\therefore$取$c=\\frac{1}{2}$即可。\n",
    "\n",
    "   $$\\therefore T(n)=\\Theta(n)$$\n",
    "\n",
    "4. $$T(n)=2T(\\frac{n}{4})+n^2$$\n",
    "   $$f(n)=\\Theta(n^2)=\\Omega(n^{lg_4 2 +c})$$\n",
    "   且$2* \\frac{n^2}{4} \\leq cn^2 \\therefore$取$c \\geq \\frac{1}{2}$即可。\n",
    "\n",
    "   $$\\therefore T(n)=\\Theta(n^2)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30c001f0",
   "metadata": {},
   "source": [
    "## 4.5-4\n",
    "$$T(n)=4T(\\frac{n}{2})+n^2 lgn$$\n",
    "$$\\because f(n)=\\Theta(n^2 lgn)$$\n",
    "取$k=1$，满足情形2，$\\therefore$可以。\n",
    "$$T(n)=\\Theta(n^2 lg^2 n)$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2 (tags/v3.10.2:a58ebcc, Jan 17 2022, 14:12:15) [MSC v.1929 64 bit (AMD64)]"
  },
  "vscode": {
   "interpreter": {
    "hash": "a166369db42c1466e2e3775def9041c304cd3bfe227c8b0f35b781bd0a6af835"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
